import org.w3c.dom.css.ElementCSSInlineStyle;

import java.awt.*;
import java.awt.font.NumericShaper;
import java.util.*;
import java.util.List;

public class LeetCode {
    public static void main(String[] args) {

    }

    //有效字母异位词
    public static boolean isAnagram(String s, String t) {

        int[] arr = new int[26];

        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i)-'a']++;
        }

        for (int j = 0; j < t.length(); j++) {
            arr[t.charAt(j)-'a']--;
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0){
                return false;
            }
        }

        return true;
    }

    //和大于target的最小子数组长度
    public static int findsize(int[] nums, int target) {

        int fast = 0;
        int slow = 0;
        int sum = 0;
        int min_len = Integer.MAX_VALUE;

        for (fast = 0; fast < nums.length; fast++) {

            sum = sum + nums[fast];
            while (sum >= target) {
                min_len = Math.min(min_len, fast - slow + 1);
                sum = sum - nums[slow];
                slow++;
            }
        }

        if (min_len == Integer.MAX_VALUE) {
            return 0;
        }
        return min_len;
    }

    public static Integer find(List<Integer> list, int k) {
        if (list == null || list.isEmpty()) {
            return null;
        }

        for (int i = 0; i < list.size(); i++) {
            Integer num = list.get(i);
            boolean is = true;
            for (int j = 0; j < list.size(); j++) {
                if (i != j) {
                    int diff = Math.abs(num - list.get(j));
                    if (diff <= k) {
                        is = false;
                        break;
                    }
                }
            }
            if (is) {
                return num;
            }
        }
        return null;
    }

    public static Integer NoRep(List<Integer> list) {
        if (list == null || list.isEmpty()) {
            return null;
        }

        Map<Integer, Integer> countMap = new HashMap<>();

        for (Integer num : list) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        for (Integer num : list) {
            if (countMap.get(num) == 1) {
                return num;
            }
        }

        return null;
    }

    public static void printList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + "->");
            cur = cur.next;
        }
        System.out.println();
    }


    public static class ListNode {

        private int val;
        private ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //反转
    public static ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;

        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static ListNode reList(ListNode head) {
        ListNode result = null;

        ListNode cur = head;

        while (cur != null) {
            ListNode pre = cur.next;
            cur.next = result;
            result = cur;
            cur = pre;
        }
        return result;
    }

    class MyLinkedList {

        int size;
        ListNode head;

        public MyLinkedList() {
            size = 0;
            head = new ListNode();
        }

        public int get(int index) {

            if (index < 0 || index > size) {
                return -1;
            }

            ListNode dummy = new ListNode();
            dummy = head;
            ListNode cur = dummy.next;

            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }

        public void addAtHead(int val) {
            ListNode dummy = new ListNode();
            dummy.next = head;
            ListNode newnode = new ListNode(val);

            newnode.next = dummy.next;
            dummy.next = newnode;

            size++;
        }

        public void addAtTail(int val) {
            ListNode newnode = new ListNode(val);
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newnode;
            size++;
        }

        public void addAtIndex(int index, int val) {
            if (index < 0 || index >= size) {
                return;
            }

            ListNode dummy = new ListNode();
            dummy.next = head;
            ListNode newnode = new ListNode(val);
            ListNode cur = dummy;

            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }

            newnode.next = cur.next;
            cur.next = newnode;

            size++;
        }

        public void delAtIndex(int index) {
            if (index >= size) {
                return;
            }

            ListNode dummy = new ListNode();
            dummy.next = head;
            ListNode cur = dummy;

            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }

            cur.next = cur.next.next;
        }
    }

    public static ListNode remNode(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}
